//==============================================================================
//	
//	Copyright (c) 2002-
//	Authors:
//	* Vojtech Forejt <vojtech.forejt@cs.ox.ac.uk> (University of Oxford)
//	
//------------------------------------------------------------------------------
//	
//	This file is part of PRISM.
//	
//	PRISM is free software; you can redistribute it and/or modify
//	it under the terms of the GNU General Public License as published by
//	the Free Software Foundation; either version 2 of the License, or
//	(at your option) any later version.
//	
//	PRISM is distributed in the hope that it will be useful,
//	but WITHOUT ANY WARRANTY; without even the implied warranty of
//	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
//	GNU General Public License for more details.
//	
//	You should have received a copy of the GNU General Public License
//	along with PRISM; if not, write to the Free Software Foundation,
//	Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
//	
//==============================================================================

package com.prism.e4.rcp.prism;

import java.util.ArrayList;
import java.util.List;

/**
 * This class represents a face (or a part of face) of a Pareto curve or its
 * underapproximation, given by it's corner points. The number of corner points
 * must be equal to the dimension, e.g. a line in a 2d, and a triangle in 3d. So
 * for example a square face must be represented as two triangle Tiles.
 */
public class Tile {
	/**
	 * The corner points that determine this Tile
	 */
	protected ArrayList<Point> cornerPoints;

	protected int dim;

	/**
	 * Creates a new Tile with a given corner points
	 * 
	 * @param cornerPoints
	 *            The number of corner points must be equal to the dimension.
	 */
	public Tile(ArrayList<Point> cornerPoints) {
		// TODO check equal dimension
		this.cornerPoints = cornerPoints;
		dim = this.cornerPoints.size();
		projectionUpperBound = new boolean[dim];
	}

	/**
	 * Returns a list containing the corner points representing this tile.
	 */
	public ArrayList<Point> getCornerPoints() {
		return this.cornerPoints;
	}

	/**
	 * If true, this tile is already known to be part of a facet of a Pareto
	 * curve, not just it's underapproximation.
	 */
	protected boolean upperBound;
	protected boolean[] projectionUpperBound;

	protected boolean hyperplaneSuggested;

	/**
	 * Returns true if this tile is already known to be part of a facet of a
	 * Pareto curve, not just its underapproximation.
	 */
	public boolean isUpperBound(int index) {
		if (index == dim)
			return this.upperBound;
		else
			return this.projectionUpperBound[index];
	}

	/**
	 * Returns true if {@code point} lies strictly above the hyperplane given by
	 * this tile.
	 */
	protected boolean pointAboveHyperplane(Point point) throws PrismException {
		// System.out.println("t: " + this);
		for (Point cp : this.cornerPoints) {
			if (point.isCloseTo(cp))
				return false;
		}

		Point w = Tile.getWeightsForTile(this);

		double productTile = 0;
		for (int j = 0; j < dim; j++)
			for (int i = 0; i < point.getDimension(); i++)
				productTile += w.getCoord(i)
						* this.cornerPoints.get(j).getCoord(i);
		productTile = productTile / point.getDimension();

		double productPoint = 0;
		for (int i = 0; i < point.getDimension(); i++)
			productPoint += w.getCoord(i) * point.getCoord(i);
		// System.out.println(productPoint + " " + productTile + " " +
		// (productPoint - productTile));
		return productPoint >= productTile + Point.SMALL_NUMBER;
	}

	/**
	 * Returns true if this tile will be changed when {@code point} is added to
	 * a parent {@link TileList}. If {@updateUpperBounds} is
	 * set, then also the information about the tile lying on a pareto curve is
	 * updated
	 * 
	 * @param updateUpperBounds
	 *            If true, the new point does not split the tile, and the tile's
	 *            corresponding hyperplane was suggested, then the information
	 *            about the tile being an upper bound is updated. This can be
	 *            either information for the whole tile or its border lines,
	 *            depending on {@code upperBoundsIndex}
	 * @param upperBoundsIndex
	 *            If equal to {@code dim}, when the information about this tile
	 *            being an upper bound is updated, the whole tile will be marked
	 *            as upper bound. If lower than {@code dim}, only the line
	 *            having zero value in {@code upperBoundsIndex}-th coordinate
	 *            will be marked as upper bound
	 * 
	 * @throws PrismException
	 * 
	 */

	public boolean processNewPoint(Point point, boolean updateUpperBounds,
			int upperBoundsIndex) throws PrismException {
		boolean ret = pointAboveHyperplane(point);

		if (ret) {
			// System.out.println("is affected: " + this);
			hyperplaneSuggested = false;
			return true;
		} else {
			if (hyperplaneSuggested && updateUpperBounds) {
				hyperplaneSuggested = false;
				if (upperBoundsIndex == this.cornerPoints.size()) {
					this.upperBound = true;
				} else
					this.projectionUpperBound[upperBoundsIndex] = true;
			}
			return false;
		}

	}

	/**
	 * Returns a list of tiles that should be added to the parent TileList when
	 * {@code point} is added, replacing the current tile. For the computation
	 * to be performed correctly, the list {@code otherPoints} must contain the
	 * set of points from all affected tiles.
	 * 
	 * @param tolerance
	 *            When the newly created tiles will differ only in a point which
	 *            is {@code tolerance} far from the original tiles, the new tile
	 *            will be considered finished.
	 */
	public List<Tile> splitByPoint(Point point, List<Point> otherPoints,
			double tolerance) throws PrismException {
		Point weights = Tile.getWeightsForTile(this);
		double pointWeight = 0;
		for (int i = 0; i < point.getDimension(); i++) {
			pointWeight += weights.getCoord(i) * point.getCoord(i);
		}

		double thisTileWeight = 0;
		for (int i = 0; i < point.getDimension(); i++) {
			thisTileWeight += weights.getCoord(i)
					* this.getCornerPoints().get(0).getCoord(i);
		}

		boolean isClose = (pointWeight - thisTileWeight) < tolerance;

		// System.out.println("SPLITTING");
		ArrayList<Tile> tiles = new ArrayList<Tile>();
		for (int i = 0; i < this.cornerPoints.size(); i++) {
			ArrayList<Point> newPoints = (ArrayList<Point>) this.cornerPoints
					.clone();
			newPoints.set(i, point);
			Tile t = new Tile(newPoints);

			boolean onBorder = true;
			for (int j = 0; j < t.cornerPoints.size(); j++) {
				onBorder = true;
				for (int k = 0; k < t.cornerPoints.size(); k++)
					if (t.cornerPoints.get(k).getCoord(j) != 0.0) {
						onBorder = false;
						break;
					}
				if (onBorder)
					break;
			}
			// System.out.println("hyperplane:" + t);

			boolean pointAboveExists = false;
			for (Point p : otherPoints) {
				// System.out.println("point " + p);
				if (t.pointAboveHyperplane(p)) {
					pointAboveExists = true;
					// System.out.println("is above");
					break;
				}

			}

			// the tile is upper bound if the original was (this is not a
			// contradiction,
			// due to the approx nature of computation even an upper bound tile
			// could be
			// improved), or is upper bound if the change is rather small.
			if (isClose || this.isUpperBound(this.dim))
				t.upperBound = true;

			if (!onBorder && !pointAboveExists)
				tiles.add(t);
		}
		// System.out.println("RET: " + tiles);
		return tiles;
	}

	/**
	 * Gets a weight vector representing the hyperplane given by the tile.
	 * 
	 * @param t
	 *            The tile to compute the weight vector for.
	 * @return
	 */
	protected static Point getWeightsForTile(Tile t) {
		int dim = t.cornerPoints.size();

		// First check if we have a nonzero point and remember one.
		int nonzeroIndex = -1;
		for (int j = 0; j < dim; j++) {
			if (!t.cornerPoints.get(j).isZero()) {
				nonzeroIndex = j;
				break;
			}
		}

		// If all are zero, we return anything meaningful
		if (nonzeroIndex == -1) {
			double[] pointCoords = new double[dim];
			pointCoords[0] = 1;
			return new Point(pointCoords);
		}

		double[][] d = new double[dim][dim];
		double[] b = new double[dim];

		for (int j = 0; j < dim; j++) {
			Point p = t.cornerPoints.get(j);
			// Zero points are problem, we change them while preserving the
			// hyperplane.
			if (p.isZero()) {
				for (int i = 0; i < dim; i++) {
					d[j][i] = t.cornerPoints.get(nonzeroIndex).getCoord(i);
				}
			} else {
				for (int i = 0; i < dim; i++) {
					d[j][i] = p.getCoord(i);
				}
			}
			b[j] = 1;
		}

		double[] ret = MultiObjUtils.solveEqns(d, b);
		double[] pointCoords = new double[dim];
		for (int i = 0; i < dim; i++)
			pointCoords[i] = ret[i];
		// System.out.println("returned points: " +
		// Arrays.toString(pointCoords));

		return new Point(pointCoords).normalize();
	}

	@Override
	public String toString() {
		StringBuffer sb = new StringBuffer();
		sb.append('{');
		for (int i = 0; i < this.cornerPoints.size() - 1; i++) {
			sb.append(this.cornerPoints.get(i).toString());
			sb.append("; ");
		}
		sb.append(this.cornerPoints.get(this.cornerPoints.size() - 1)
				.toString());
		sb.append('}');
		return sb.toString();
	}

	/**
	 * True if there is one of the boundaries of the Tile is a line orthogonal
	 * to {@code index}'s axis
	 */
	public boolean liesOnBoundary(int index) {
		int count = 0;

		for (Point p : this.cornerPoints) {
			if (p.getCoord(index) == 0)
				count++;
		}

		// System.out.println(count);

		/*
		 * //this can happen in fact in all zeros if (count == 3) { throw new
		 * Error(
		 * "Error in design of Pareto curve algorithm. The whole Tile lies on a boundary."
		 * ); }
		 */

		return (count >= 2);

	}
}
